package 动态规划;

public class LeetCode91_解码方法 {
    public static int numDecodings(String s) {
        if(s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[s.length()+1];
        char[] charArray = s.toCharArray();
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 1; i < s.length(); i++) {
            if(charArray[i] == '0') {
                if(charArray[i-1] == '1' || charArray[i-1] == '2' ) {
                    // dp数组比s多一位
                    // 这里不能是 dp[i+1] = dp[i] 因为如果i和i-1可以组成一个，并且i可以单独一个，他的个数就会比i+i多一个，所以要dp[i+1] = dp[i-1],因为确保不能0开头。
                    dp[i+1] = dp[i];
                } else {
                    return 0;
                }
            } else if(charArray[i-1] == '1' || (charArray[i-1] == '2'
                    && charArray[i] - '0' > 0 && charArray[i] - '0' < 7)) {
                dp[i+1] = dp[i] + dp[i-1];
            } else {
                dp[i+1] = dp[i];
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        String s = "2101";
        int count = numDecodings(s);
        System.out.println(count);
    }
}
